package com.mango.algorithm.sort;

import com.google.common.base.Stopwatch;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.concurrent.TimeUnit;

/**
 * 优先队列排序
 * 实质就是堆排序
 * 大根堆，小根堆
 * 堆操作：heapInsert(入堆）, heapify（堆化）
 */
public class PriorityQueueSort {
    public static void main(String[] args) {
        Stopwatch sw = Stopwatch.createStarted();
        int[] nums = {13,7,4,6,9,24,12,3,5,2,11,22,41,23,12,18};
        System.out.println("old:"+ Arrays.toString(nums));
        System.out.println("result:"+Arrays.toString(sort(nums))+"耗时:"+sw.elapsed(TimeUnit.MILLISECONDS)+"ms");

    }

    public static int[] sort(int[] nums){
        // 优先队列排序
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int num : nums){
            queue.offer(num);
        }
        int i=0;
        while (!queue.isEmpty()){
            nums[i] = queue.poll();
            i++;
        }
        return nums;
    }
}
